package demo;

import java.util.Objects;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 38917
 * Date: 2025-02-17
 * Time: 14:01
 */
class Person{
    public int age;

    public Person(int age) {
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age;
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(age);
    }
}

public class HashBuck<k,v> {

    static class Node<k,v>{
        public k key;
        public v val;
        public Node<k,v> next;

        public Node(k key, v val) {
            this.key = key;
            this.val = val;
        }
    }

    private Node<k,v>[] array;
    public int useSize;

    public HashBuck() {
        this.array = (Node<k, v>[]) new Node[10];
    }
    //
    public void put(k key,v val){
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<k,v> cur = array[index];
        while (cur != null){
            //应对哈希冲突
            if(cur.key.equals(key)){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //头插法
        Node<k,v> node = new Node<>(key, val);
        node.next = array[index];
        array[index] = node;
        useSize++;
        //判断负载因子是否大于0.75
        if (loadFactors() > 0.75){
            //开散列
            reSize();
        }
    }
    //负载因子
    public double loadFactors(){
        return useSize * 1.0 / array.length;
    }
    //
    public void reSize(){
        Node<k,v>[] tempArray = (Node<k, v>[]) new Node[array.length * 2];
        for (Node<k, v> kvNode : array) {
            Node<k, v> cur = kvNode;
            while (cur != null) {
                Node<k, v> curNext = cur.next;
                int hash = cur.key.hashCode();
                int newIndex = hash % tempArray.length;
                cur.next = tempArray[newIndex];
                tempArray[newIndex] = cur;
                cur = curNext;
            }
        }
        array = tempArray;
    }
    //
    public v get(k key){
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<k,v> cur = array[index];
        while (cur != null){
            if (cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}


















